AustralieFrV1, Main, Exploration, bibRecord, 006391

Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

Identifieur interne : 006391 ( Main/Exploration ); précédent : 006390; suivant : 006392

Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

Auteurs : Damien Stehlé [France] ; Ron Steinfeld [Australie]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.

RBID : ISTEX:DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88

Descripteurs français

Wicri :
- topic : Cryptographie.

English descriptors

KwdEn :
- Algorithm, Chinese remainder theorem, Cryptographic, Cryptography, Cyclic lattices, Cyclotomic, Decryption, Decryption algorithm, Discrete gaussian, Discrete gaussian distribution, Discrete gaussians, Dz2n, Encryption, Encryption scheme, Encryption schemes, Errors problem, Factors modulo, Future work, Gaussian, Generation algorithm, Hardness, Heidelberg, Ideal lattice, Ideal lattices, Invertible, Lattice, Lattice problems, Linear factors modulo, Lncs, Lyubashevsky, Matrix, Micciancio, Modulo, Ntru, Ntruencrypt, Outputs samples, Peikert, Quantum hardness, Regev, Regularity, Regularity result, Resp, Rntru, Springer, Standard deviation, Standard model, Standard problems, Statistical distance, Stehl, Steinfeld, Success probability, Whole ring.
Teeft :
- Algorithm, Chinese remainder theorem, Cryptographic, Cryptography, Cyclic lattices, Cyclotomic, Decryption, Decryption algorithm, Discrete gaussian, Discrete gaussian distribution, Discrete gaussians, Dz2n, Encryption, Encryption scheme, Encryption schemes, Errors problem, Factors modulo, Future work, Gaussian, Generation algorithm, Hardness, Heidelberg, Ideal lattice, Ideal lattices, Invertible, Lattice, Lattice problems, Linear factors modulo, Lncs, Lyubashevsky, Matrix, Micciancio, Modulo, Ntru, Ntruencrypt, Outputs samples, Peikert, Quantum hardness, Regev, Regularity, Regularity result, Resp, Rntru, Springer, Standard deviation, Standard model, Standard problems, Statistical distance, Stehl, Steinfeld, Success probability, Whole ring.

Abstract

Abstract: NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers could make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security. In the present work, we show how to modify NTRUEncrypt to make it provably secure in the standard model, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. Our main contribution is to show that if the secret key polynomials are selected by rejection from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its domain. The security then follows from the already proven hardness of the the R-LWE problem.

Url:

https://api.istex.fr/document/DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88/fulltext/pdf

DOI: 10.1007/978-3-642-20465-4_4

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Istex, to step Corpus: 002973
to stream Istex, to step Curation: 002973
to stream Istex, to step Checkpoint: 000810
to stream Main, to step Merge: 006767
to stream Main, to step Curation: 006391

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Making NTRU as Secure as Worst-Case Problems over Ideal Lattices</title>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</author>
<author><name sortKey="Steinfeld, Ron" sort="Steinfeld, Ron" uniqKey="Steinfeld R" first="Ron" last="Steinfeld">Ron Steinfeld</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-20465-4_4</idno>
<idno type="url">https://api.istex.fr/document/DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002973</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002973</idno>
<idno type="wicri:Area/Istex/Curation">002973</idno>
<idno type="wicri:Area/Istex/Checkpoint">000810</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000810</idno>
<idno type="wicri:doubleKey">0302-9743:2011:Stehle D:making:ntru:as</idno>
<idno type="wicri:Area/Main/Merge">006767</idno>
<idno type="wicri:Area/Main/Curation">006391</idno>
<idno type="wicri:Area/Main/Exploration">006391</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Making NTRU as Secure as Worst-Case Problems over Ideal Lattices</title>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>CNRS, Laboratoire LIP (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL), 46 Allée d’Italie, 69364, Lyon Cedex 07</wicri:regionArea>
<placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
<settlement type="city">Lyon</settlement>
</placeName>
</affiliation>
<affiliation></affiliation>
</author>
<author><name sortKey="Steinfeld, Ron" sort="Steinfeld, Ron" uniqKey="Steinfeld R" first="Ron" last="Steinfeld">Ron Steinfeld</name>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, NSW</wicri:regionArea>
<wicri:noRegion>NSW</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Australie</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2011</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Chinese remainder theorem</term>
<term>Cryptographic</term>
<term>Cryptography</term>
<term>Cyclic lattices</term>
<term>Cyclotomic</term>
<term>Decryption</term>
<term>Decryption algorithm</term>
<term>Discrete gaussian</term>
<term>Discrete gaussian distribution</term>
<term>Discrete gaussians</term>
<term>Dz2n</term>
<term>Encryption</term>
<term>Encryption scheme</term>
<term>Encryption schemes</term>
<term>Errors problem</term>
<term>Factors modulo</term>
<term>Future work</term>
<term>Gaussian</term>
<term>Generation algorithm</term>
<term>Hardness</term>
<term>Heidelberg</term>
<term>Ideal lattice</term>
<term>Ideal lattices</term>
<term>Invertible</term>
<term>Lattice</term>
<term>Lattice problems</term>
<term>Linear factors modulo</term>
<term>Lncs</term>
<term>Lyubashevsky</term>
<term>Matrix</term>
<term>Micciancio</term>
<term>Modulo</term>
<term>Ntru</term>
<term>Ntruencrypt</term>
<term>Outputs samples</term>
<term>Peikert</term>
<term>Quantum hardness</term>
<term>Regev</term>
<term>Regularity</term>
<term>Regularity result</term>
<term>Resp</term>
<term>Rntru</term>
<term>Springer</term>
<term>Standard deviation</term>
<term>Standard model</term>
<term>Standard problems</term>
<term>Statistical distance</term>
<term>Stehl</term>
<term>Steinfeld</term>
<term>Success probability</term>
<term>Whole ring</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Chinese remainder theorem</term>
<term>Cryptographic</term>
<term>Cryptography</term>
<term>Cyclic lattices</term>
<term>Cyclotomic</term>
<term>Decryption</term>
<term>Decryption algorithm</term>
<term>Discrete gaussian</term>
<term>Discrete gaussian distribution</term>
<term>Discrete gaussians</term>
<term>Dz2n</term>
<term>Encryption</term>
<term>Encryption scheme</term>
<term>Encryption schemes</term>
<term>Errors problem</term>
<term>Factors modulo</term>
<term>Future work</term>
<term>Gaussian</term>
<term>Generation algorithm</term>
<term>Hardness</term>
<term>Heidelberg</term>
<term>Ideal lattice</term>
<term>Ideal lattices</term>
<term>Invertible</term>
<term>Lattice</term>
<term>Lattice problems</term>
<term>Linear factors modulo</term>
<term>Lncs</term>
<term>Lyubashevsky</term>
<term>Matrix</term>
<term>Micciancio</term>
<term>Modulo</term>
<term>Ntru</term>
<term>Ntruencrypt</term>
<term>Outputs samples</term>
<term>Peikert</term>
<term>Quantum hardness</term>
<term>Regev</term>
<term>Regularity</term>
<term>Regularity result</term>
<term>Resp</term>
<term>Rntru</term>
<term>Springer</term>
<term>Standard deviation</term>
<term>Standard model</term>
<term>Standard problems</term>
<term>Statistical distance</term>
<term>Stehl</term>
<term>Steinfeld</term>
<term>Success probability</term>
<term>Whole ring</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Cryptographie</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers could make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security. In the present work, we show how to modify NTRUEncrypt to make it provably secure in the standard model, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. Our main contribution is to show that if the secret key polynomials are selected by rejection from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its domain. The security then follows from the already proven hardness of the the R-LWE problem.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
</country>
<region><li>Auvergne-Rhône-Alpes</li>
<li>Rhône-Alpes</li>
</region>
<settlement><li>Lyon</li>
</settlement>
</list>
<tree><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</region>
</country>
<country name="Australie"><noRegion><name sortKey="Steinfeld, Ron" sort="Steinfeld, Ron" uniqKey="Steinfeld R" first="Ron" last="Steinfeld">Ron Steinfeld</name>
</noRegion>
<name sortKey="Steinfeld, Ron" sort="Steinfeld, Ron" uniqKey="Steinfeld R" first="Ron" last="Steinfeld">Ron Steinfeld</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006391 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006391 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Asie
   |area=    AustralieFrV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88
   |texte=   Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
}}

This area was generated with Dilib version V0.6.33.
Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024

	Serveur d'exploration sur les relations entre la France et l'Australie
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur les relations entre la France et l'Australie

Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri